1. Field of the Invention
The present invention concerns with a data processing method and device which are capable of serializing the access for sharing a data list among the concurrently-operating processes under the multiprocessing or multiprogramming environment run on a computer. More particular, the invention concerns with the data processing method and device which can properly match the serialization of access to the shared data list to a tightly-coupled multiprocessor environment, in which two or more instruction processors share a main storage.
2. Description of the Prior Art
The multiprocessing or multiprogramming environment run on a computer makes it possible to run many processes concurrently. Hereinafter, the term "process" refers to a unit of work done when an operating system performs the assignment of a central processing unit (CPU). In general, a term "task" is often used for representing the same meaning.
In operation, the process requires various kinds of resources such as a CPU, a memory, an input and output device, and the like. Since, however, these resources are shared by two or more processes, a conflict often takes place among these processes in accessing the resources.
In a program, these resources are, in general, represented as data blocks saved in a main storage (virtual storage). Hence, the conflict caused in accessing the resources is embodied as the conflict caused in accessing a list (data list) of each data block. The element processing executed in accessing the data list consists of insertion of a list element, retrieval of a list element, and deletion of a list element. The general operation can be realized by the series of element processings. The operating system has to provide a mechanism for executing the serialization of access to these data lists.
One example of this mechanism is described in S. E. Madnick et al. "Operating Systems" chapter 4.5, McGraw-Hill edition, 1974. As described in the example, a typical mechanism for executing the serialization of access to a data list can be realized by a series of instructions referred to as "lock" and "unlock". This mechanism provides status variables referred to as a lock byte or a lock word, which represents the corresponding data list.
In locking operation, a lock-request process takes the steps of checking the status variable and, if not used, changing the state to "in use" or, if used, waiting until it is not used. In unlocking operation, it takes the steps of changing the status variable from in use to not used and, if necessary, reporting a lock release to another process waiting for a lock.
In this mechanism, the process obtaining a lock includes an exclusive access capability for a data list, while the other processes cannot access the data list until the lock-obtaining process release the lock. In the meantime, the lock-waiting process interrupts the execution, resulting in being suspended or spinning, that is, iteratively checking status variables. In either case, the data processing is temporarily interrupted under this process.
For referencing or updating the status variables, this mechanism employs a machine instruction called as a read-modify-write type instruction which instructs the operation "read-compare-change-write" of a variable to be executed as a combined one. That is, while a process checks that a state variable is not in use and changes the status variable to be an in-use one, this mechanism is used for preventing the same status variable from being rewritten by another process. For example, in a HITAC M series computer, the machine instructions are a TS (Test and Set) instruction, a CS (Compare and Swap) instruction and a CDS (Compare Double and Swap) instruction.
An improvement of the "lock/unlock" mechanism is a mechanism in which a lock has a plurality of modes. This mechanism provides a shared mode lock and an exclusive mode lock. The process obtaining a shared mode lock is capable of merely referencing a data list, while the process obtaining an exclusive mode lock is capable of referencing and updating a data list. A plurality of processes can obtain the shared mode lock concurrently. The shared mode lock is contradictory to the exclusive mode lock as the exclusive mode locks are contradictory to each other. This mechanism is superior to the foregoing simple "lock/unlock" mechanism in that the former can execute the element processing of a data list concurrently even if a plurality of retrieval processings come into conflict with one another in one data list. Yet, only the sequential execution is allowed if the conflict is caused in the other processings except the retrieval one.
The Japanese First Publication No. 62-92061 discloses a mechanism by which the insertion, retrieval and deletion processings can be all executed for a data list concurrently. This mechanism provides a status variable containing discontinuous words. The element processing of a data list is separated into a start processing to be executed concurrently and a finish processing to be executed only sequentially.
A process serves to change the status variable and executes the start processing about a data list. In this case, another process may execute the start processing concurrently. If no other process comes into conflict with the current process, the process executes the finish processing, but if another process comes into conflict, it directly finishes the processing after cancelling the finish processing. Then, any one of the conflicted processes picks up and completes the cancelled processing.
This mechanism is referred to as "obligation passing", which is controlled by the partial change of the status variable. For the processing of the data list, no "obligation passing" is required about the insertion of a list element into a defined one end and the retrieval of any list element. About the deletion of a list element, the processing is separated into a logical deletion processing for setting an invalid flag to a list element and an actual deletion processing for releasing a list element out of a pointer chain, the latter of which is subject to the "obligation passing". Herein, the "obligation passing" is implemented by inserting a list element to a pointer chain for chaining the elements to be deleted, which pointer chain is provided independently of the pointer chain representing a data list.
The foregoing simple lock mechanism is capable of keeping only one process obtaining the lock alive, that is, interrupts the other processes if two or more processes comes into conflict with one another in requesting the lock obtaining. This function brings about the significant degradation of performance as in a tightly-coupled multiprocessor environment in which a plurality of instruction processors share a main storage. The two-mode lock mechanism may suppress the probability of conflict of locks involving the interruption of a process. The suppressing degree, however, is not sufficient.
The use of the "obligation passing" mechanism makes it possible to reference or update a data list without interrupting the process, though, it merely applies to a limited range of processings. That is, the application of the mechanism is limited to the processing which can be properly separated into a start processing to be executed concurrently by a plurality of processes and a finish processing to be processed sequentially and, if a conflict takes place among the processes, to be processed by the other process temporarily after cancelling the finish processing.
Hence, for example, in case the element has been already picked out of the pointer chain when a deletion request of a list element is issued, the "obligation passing" mechanism is ineffective. Such a case needs a processing in which an element deleted from the data list has been serially used in the same process. And, this mechanism provides more overhead of an individual itself in compensation for the upgraded concurrent processing level than the simple lock mechanism. Hence, in case all the elements in a data list are processed in the lump and in large quantity and a complicated manner, for example, this mechanism may lower its overall processing capability as a result. In such a case, the mechanism obtaining the lock and executing the processings in the lump can offer higher degree of freedom for processing and easily suppress the overhead.